1. Field of the Invention
The present invention relates to a computer system, and more particularly, to the field of a memory management method in the computer system. Specifically, the present invention relates to a generational garbage collection method and the computer system using the same method.
2. Description of the Prior Art
All the application programs are written using various resources. For example, in an object-oriented programming environment, a resource is handled as an object. A programmer reserves a memory explicitly for every object and initializes a memory block that corresponds to the object, then uses the object at program execution. After use, the programmer discards object status information and finally releases the memory to which the object is allocated. These memory management operations by programmers, however, are possible causes of bugs, and a fatal programming error, such as a memory leak and damage of an object remains to be a possibility.
An object-oriented programming system that has been used frequently in recent years to free a programmer from troublesomeness of memory management performs memory management automatically and dynamically. An object-oriented language processing system (programming system, hereinafter referred to as the system merely) manages a memory of a limited size called a heap and automatically and dynamically allocates an object to the heap. Because an object is allocated continuously by the system to the heap when an application program is executed, a limited heap will be exhausted someday. To solve this problem, a memory block not used in the heap has to be collected and reused by garbage collection.
Usually, in an object-oriented programming environment, when a pointer to an object in the heap (memory locating information) is lost, the object cannot be accessed. Therefore a memory block in the heap allocated to the inaccessible object can be reused for another object. Based on this fact, garbage collection identifies an accessible object during an application program is running and holds the object as a live object if the object can be accessed. An inaccessible object is released for subsequent heap allocation as an unnecessary object and the memory block is reused later.
Whether an object can be accessed or not is determined by tracing its root. All the application programs have roots. A root is a memory locating information list and refers to one of an object in a heap and an object (not referred to from an application program) for which a null in the heap is set. For example, all the global static object pointers in an application program, local variable and argument object pointers on a stack, and all the CPU registers that store a pointer that indicates the object in the heap are regarded as part of the root of the application program. Garbage collection determines that the object can be accessed by tracing the root if the object can be reached from the root.
Various garbage collection methods are proposed. Regarding these conventional methods, an explanation is omitted here because the details are described in the “Garbage Collection: Algorithms for Automatic Dynamic Memory Management” (ISBN 0-147-94148-4) written by Richard Jones and Rafael Lins and published by John Wiley & Sons. In this literature, an object-oriented programming system of recent years adopts generational garbage collection as a method for performing the garbage collection most efficiently.
The generational garbage collection is assumed that most objects live short, and the newer an object is, the shorter a period for existence is, but the older an object is, the longer even a period for existence is. Under this assumption, the time duration when application program execution is interrupted by the garbage collection is reduced by limiting the number of objects to be checked when the garbage collection is executed, that is, the size of a memory to which an object for the garbage collection is allocated.
The generational garbage collection divides a heap logically into multiple groups called a generation and manages it. The generation relates to a period for existence of an object and, in general, is decided depending on a garbage collection cycle in which the object lived. For example, when the heap is divided logically into two groups of a new generation and an old generation, the latest object is allocated in the memory block of a new-generation heap, and the object that lives even after the garbage collection was performed several times is copied to the memory block of an old-generation heap. Usually, the garbage collection is performed only for the new-generation heap (minor collection). Only when there is no memory block allocated to a new object in the new-generation heap, the garbage collection is performed for the heap including at least the old-generation heap (major collection). The minor collection is performed when the size of a memory to which a new object is allocated reaches a predetermined threshold or a predetermined time elapses during application program execution and performed more frequently than the major collection. The minor collection identifies an inaccessible object in an object group to which the memory block of the new-generation heap for the garbage collection is allocated by tracing its root and copies the accessible object to another place. Further, the minor collection copies an long-life object to the old-generation heap.
In general, copying indicates processing that copies an accessible object to another memory block. In order that an application program can access an object in a new location even after copy processing, the object pointer is moved to the memory block in the new location. In the minor collection, because the number of objects to be copied is very small in comparison with the major collection, the garbage collection can be performed in a short period.
FIG. 1 shows an example of a generational garbage collection system that divides a heap logically into two groups of an old generation and a new generation. In the drawing, 100 is a heap memory, 101 is an old-generation heap, and 102 is a new-generation heap. The new-generation heap 102 is further divided logically into an object creating area 110 and an aging area 111. Further, as shown in the drawing, the new-generation heap also includes an area that is not used yet. 120, 130, and 140 are objects allocated in the heap, and indicate the same contents in the drawing.
A new object is allocated to the object creating area 110. The object that lived as a result of having performed the minor collection in the object creating area 110 is copied to the aging area 111. The live object that was able to be accessed even after a fixed garbage collection cycle in the aging area 111 is relocated to the old-generation heap 101.
The new object 120 is allocated to the object creating area 110. As a result of the minor collection in the object creating area 110, if the object 120 can be accessed from an application program, the object 120 is copied as the object 130 of the aging area 111 and a pointer is updated. As a result of copying, the object 120 in the object creating area 110 is invalid and the object 130 is referred to from the application program. If the object 130 in the aging area 111 can be accessed even after a fixed garbage collection cycle, the object 130 is relocated as the object 140 in the old-generation heap 101. After the relocation, the object 140 is referred to from the application program.
FIG. 2 shows another example of a generational garbage collection system that divides a heap logically into three generations. In the drawing, 200 indicates a heap, 201 indicates a zeroth generation heap, 202 indicates a first generation heap, and 203 indicates a second generation heap. 210, 211, and 212 indicate objects and include the same contents. A new object is allocated to the zeroth heap 201. The object that lived during at least an N (N is an integer of 1 to 4) garbage collection cycle in the zeroth generation heap is relocated to the first generation heap 202 copies. The second generation heap 203 holds the oldest object in the system. The object that lived during at least an N (N is an integer of 1 to 4) garbage collection cycle in the first generation heap 202 is relocated to the second generation heap. Usually, N is set to 1.
The new object 210 is allocated to the zeroth generation heap 201. After a fixed garbage collection cycle, if the object 210 in the zeroth generation heap can be accessed from an application program, the object 210 is copied as the object 211 of the first generation heap 202. As a result of coping, the object 210 in the object creating area 201 becomes invalid and the object 211 is referred to from the application program. If the object 211 in the first generation heap 202 can be accessed even after the fixed garbage collection cycle, the object 211 is copied as the object 212 in the second generation heap 203. After the copying, the object 212 is referred to from the application program.
Regarding the aforementioned generational garbage collection method, the following conventional examples are well known.
For example, in U.S. Pat. No. 6,199,075, a method of performing generational garbage collection in a multiprocessor environment is described. When a specific processor detects a condition under which the generational garbage collection is performed to perform the garbage collection in the multiprocessor environment and the condition is taken, multiple processors stop program processing in accordance with an instruction of the specific processor and perform the generational garbage collection simultaneously. When the multiple processors detect that the garbage collection terminated, program processing is resumed. The generational garbage collection uses a method of dividing the heap shown in FIG. 1 into two groups of anew generation and an old generation and further dividing the new generation into an object creating area and an aging area. At minor collection, whether or not each object in the object creating area can be accessed from an application program is identified and the live object in the object creating area that was accessible is copied to the aging area. The object in the aging area that can be accessed even after an N (N is an integer of 1 to 4) garbage collection cycle is copied to the old-generation heap. (First well-known example) In U.S. Pat. No. 5,652,883, a method of accurately identifying an object that lives at minor collection by merging a generational garbage collection method and a conservative garbage collection approach is described. A memory includes a stack and a heap. The heap is divided logically into a new generation and an old generation, and new and old objects identified by a pointer are allocated to each generation. The stack holds what may be an object pointer in the entry.
What may be the object pointer is held indicates the following reason. For example, an object is defined as a union with an object reference and a value. In this case, the contents may be the pointer and the value when the object is referred to. In the conservative garbage collection, it is identified that both the pointer and value can be accessed. As a result, when the object that lived at garbage collection is compressed and relocated to another memory area, an object which is not a pointer cannot be moved because an address is not identified. Accordingly, the conventional method described here uses a method for accurately determining whether the pointer can be accessed or not and solving a problem by managing the pointer independently of what may be the pointer.
Further, a remember list is provided to support the object reference of a new-generation heap from an old-generation heap that cannot be traced from the root of the new-generation heap. The object in the old-generation heap having the pointer to the object in the new-generation heap is registered in the remember list. At garbage collection, the object that can be accessed via a stack and the remember list is identified as a live object. This method identifies the live object more accurately by determining at garbage collection whether an object for the garbage collection can be accessed or not using a stack entry and the remember list as well as using the root of the new-generation heap. Minor collection relocates the live object identified by the aforementioned method to an older generation. (Second well-known example)
In U.S. Pat. No. 6,226,653 B1, a generational garbage collection method that makes a reference from the object in the old-generation heap to the object of the new-generation heap efficiently using a remember set is described. In this literature, a method of dividing the heap shown in FIG. 2 logically into three generations is used. The remember set is used to register the old-generation heap having the pointer into the new-generation object in the same example as the second well-known example. Once an object is copied to the old-generation heap, even if an application program does not access the object, because the object is not collected until major collection is executed, the old-generation heap cannot be used effectively. Accordingly, to reduce the number of objects copied to the old-generation heap as much as possible, an intermediate generation located between the new generation and the old generation is provided and the copy timing between the respective generations is delayed, then the number of objects copied to the old generation is reduced. (Third well-known example)
As a method of reducing overheads of the minor collection, in the “Generational Garbage Collection Based on a Theoretical Analysis on an Object Live Ratio” of the Proceedings of the Information Processing Society of Japan Vol. 38 No. Apr. 4, 1997, pp. 835 to 844, a generational garbage collection method that dynamically changes a threshold called a watermark based on an object live ratio in the minor collection is disclosed. In this literature, a method of dividing a heap logically into two groups of a new generation and an old generation and further dividing the new-generation into an object creating area and an aging generation is used. By setting a threshold address called the watermark, an object that can be accessed in a lower address than the threshold at minor collection is copied directly to the old-generation heap and the object that can be accessed in a higher address than the threshold is copied to the aging area of the new-generation heap. In this literature, the system is dynamically set based on a theoretical calculation as to how long the object outlives the watermark. (Fourth well-known example)
In the generational garbage collection methods described in the aforementioned first, second, and third well-known examples, it is assumed that periods for existence of most objects are short, and the newer an object is, the shorter a period for existence is, but the older an object is, the longer even a period for existence is. In other words, in minor collection, it is assumed that there are only a few live objects to be relocated (copied), and, as a result, there are also few objects to be copied to the old-generation heap. Under the assumption, a method for accurately identifying a live object to be copied in the minor collection is described.
In a business information system of the broadband age, however, many application programs need to be developed in a short time. Therefore the tuning time of an individual application program is reduced. Further, when a new application program starts running on the business information system, the, application program seldom changes because it is difficult to stop the operation and maintain the system. In the program developed under such a condition, the period for existence of an object is prolonged. Further, in the business information system of the broadband age, because the application program is accessed via a network, the live period of the object is prolonged intrinsically. In the program in which the live period of an object is long, there are many live objects identified to be accessible as a result of minor collection and an amount of relocation of an intra- or inter-generation object, that is, an amount of copying increases.
For example, in the generational garbage collection composed of the zeroth, first, and second generations as shown in the aforementioned third well-known example, when there are many live objects, most new objects for minor collection are copied from the zeroth generation to the first generation, and further these objects are copied from the first generation to the second generation as they are. Otherwise, as shown in the aforementioned first well-known example, in the generational garbage collection composed of new and old two generations and in which the new generation is further composed of an object creating area and an aging area, most objects are copied from the object creating area to the aging area at minor collection and further copied from the aging area to an old-generation area. That is, great many objects perform relocation processing (copy processing) twice or more. Because the interrupt time of the application program in the minor collection is minimized in particular, the copy processing may be performed in parallel with the application program processing. In such a case, the copy processing that occurs by relocation adversely affects the processing of the application program and the performance of the application program deteriorates greatly. In the aforementioned first, second, and third well-known examples, because it is assumed that there Are few live objects at minor collection, the copy processing hardly affects the application program processing. In the application program of the broadband age having many live objects, the inter-generation copy processing of an object increases, and, consequently, the performance of the application program deteriorates.
The fourth well-known example is described below. In a prior art, it is assumed that garbage collection processing is performed by interrupting program processing. Under the assumption, based on a theoretical calculation indicating that how long an object outlives, the optimum value of a watermark is decided and overheads of the garbage collection are reduced. In reality, however, to minimize a program interrupt time by the garbage collection processing, the copy processing part of the garbage collection processing may be performed in parallel with the program processing. In this prior art, because the deterioration of the processing performance of the application program caused by the fact that the copy processing is performed in parallel with the prime processing of the program is not taken into consideration, it is difficult to decide the optimum threshold. Further, to change a copy destination using a threshold address, even when most objects live in an object creating area, an object allocated to a higher address than the threshold address is copied to the aging area of the new-generation heap, and, therefore, an amount of copying cannot be reduced.
To solve this problem, when there are many accessible objects in the minor collection, that is, when the block size of a memory to be copied is large, the copy processing needs to be reduced by changing a copy destination of an object.
Further, a measure can be taken for the problem of the performance deterioration of an application program by tuning a source code level, such as redesigning the application program, releasing an unnecessary object or not generating an unnecessary object, or reusing the object. However, the source code level, tuning increases a program development cost.
To solve this problem, even when there are many accessible live objects at minor collection, the processing time of an application program needs to be reduced without changing the application program.
In order to prevent the performance deterioration of the application program of the broadband age, a first issue of the present invention is, when there are many accessible live objects from the application program in the minor collection of generational garbage collection, to provide a generational garbage collection method that reduces the relocation processing (that is, copy processing) of the objects.
A second issue of the present invention is to provide a parameter setting method of the generational garbage collection by which a programmer can set a threshold for changing a copy destination of an object without modifying a source code of the application program.